凸优化 (2021年秋季)

第1周，9月14日，课程简介，凸优化问题介绍 讲义下载，本节内容由邓展望协助准备 demo: sparse_l1_example.m

第2周，9月21日，中秋节放假

第2周，9月23日，凸集的定义和判别 讲义下载，本节内容由丁思哲协助准备 read chapter 2 in the book “Convex optimization”.

第3周，9月28日，凸函数的定义和判别 讲义下载，本节内容由华奕轩协助准备 read chapter 3 in the book “Convex optimization”.

第4周，10月5日，国庆节放假

第4周，10月7日，国庆节放假

第5周，10月12日，数值代数基础，向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解 讲义下载，本节内容由张轩熙协助准备 numerical algebraic background 请读非线性规划参考材料 demo: demo_linalg.m Demo: Sparse matrix-dense vector products using intel MKL BLAS (Basic Linear Algebra Subprograms) LAPACK (Linear Algebra PACKage) Intel Math Kernel Library – Documentation Call LAPACK and BLAS Functions in Matlab

第6周，10月19日，典型的凸优化问题 讲义下载，本节内容由邓展望协助准备 read chapter 4 in in the book “Convex optimization”

第6周，10月21日，线性规划，二次锥规划，半定规划简介: lecture notes 线性规划，二次锥规划，半定规划例子: lecture notes 凸优化模型语言和算法软件，CVX, SDPT3, Mosek, CPLEX, Gruobi Prof. Boyd lecture notes on Disciplined convex programming and CVX read chapter 4 in in the book “Convex optimization” Introduction on Linear Programming (LP), read Chapter 1 in “Introduction to Linear Optimization” by Dimitris Bertsimas and John N. Tsitsiklis. Second-order Cone Programming (SOCP), read section 2 in “Second-order cone programming” Semidefinite Programming (SDP), read section 3 in “SDP-M-J-Todd” and section 2 in “SDP-Lieven-Boyd” The max cut paper by Goemans and Williamson 模型语言： CVX, YALMIP LP, SOCP, SDP典型算法软件: SDPT3, MOSEK, CPLEX, GUROBI NLP 典型算法软件: Ipopt, KNITRO Decision Tree for Optimization Software

第7周，10月26日，对偶理论, 凸优化最优性条件 讲义下载，本节内容由谢中林协助准备 read chapter 5 in in the book “Convex optimization” Lagrangian function, Lagrangian dual problem, examples max cut problem: dual of nonconvex problem, SDP relaxation: the dual of the dual duality using problem reformulation

第8周，11月2日，对偶理论, 凸优化最优性条件

第8周，11月4日，梯度法和线搜索算法，最速下降法及其复杂度分析，线搜索算法，Barzilar-Borwein 方法 讲义下载，本节内容由谢中林协助准备 Complexity analysis: Yu. Nesterov, Introductory Lectures on Convex Optimization. A Basic Course (2004), section 2.1. Line search: “Numerical Optimization”, Jorge Nocedal and Stephen Wright, chapter 3: 3.1, 3.5 Barzilar-Borwein Method: “Optimization Theory and Methods”, Wenyu Sun, Ya-Xiang Yuan, section 3.1.3 Matlab code on the BB method with nonmonotone line search

第9周，11月9日，次梯度 讲义下载，本节内容由朱桢源协助准备

第10周，11月16日， 次梯度算法，讲义下载，本节内容由朱桢源协助准备

第10周，11月18日，期中考试

第11周，11月23日， 近似点算子的构造和性质 讲义下载，本节内容由陈乐恒，朱桢源协助准备

第12周，11月30日，近似点梯度法的构造和分析，条件梯度法, inertial proximal method 讲义下载，本节内容由陈乐恒，朱桢源协助准备 “Proximal Algorithms”, N. Parikh and S. Boyd, Foundations and Trends in Optimization, 1(3):123-231, 2014. 条件梯度法参考： 王奇超,文再文,蓝光辉,袁亚湘, 优化算法复杂度分析简介, (paper) Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock, iPiano: Inertial Proximal Algorithm for Nonconvex Optimization, SIAM J. IMAGING SCIENCES, Vol. 7, No. 2

第12周，12月2日， Nesterov加速算法和分析 讲义下载，本节内容由李煦恒协助准备 Prof. Lieven Vandenberghe's lecture notes on smoothing 王奇超,文再文,蓝光辉,袁亚湘, 优化算法复杂度分析简介, (paper) Paul Tseng, Approximation accuracy, gradient methods, and error bound for structured convex optimization, Math. Program., Ser. B (2010) 125:263–295 参考文献： Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems Weijie Su, Stephen Boyd, E. Candes, A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights

第13周，12月7日， 增广拉格朗日函数法 讲义下载，本节内容由陈乐恒，丁思哲协助准备

第14周，12月14日， 近似点算法 讲义下载，本节内容由陈乐恒，邓展望协助准备

第14周，12月16日，对偶算法 讲义下载，本节内容由朱桢源协助准备

第15周，12月21日，交替方向乘子法 讲义下载，本节内容由华奕轩协助准备 “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”, S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Foundations and Trends in Machine Learning, 3(1):1–122, 2011 Daniel O'Connor, Lieven Vandenberghey, On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting

第16周，12月28日， Block Coordinate Descent Methods 讲义下载，本节内容由朱桢源协助准备 Jérôme Bolte, Shoham Sabach, Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems

第16周，12月30日， semi-smooth Newton methods 讲义下载，本节内容由李勇锋，邓展望协助准备